The present invention concerns a method of controlling errors in packets transmitted on at least one transmission link between a transmitter and a receiver. The present invention applies essentially in cases where the said link can support a plurality of virtual circuits.
The present invention applies to a transmission system of the type depicted in FIG. 1. In this FIG. 1, a transmitter 10 can be seen which receives, from an input multiplex 11, packets which may belong to several different virtual circuits. This transmitter 10 transmits, to a receiver 30 via a transmission line 20, the packets which it receives from the multiplex 11, in the form of a sequence of packets. On receiving the packets from the transmission line 20, the receiver 30 implements a method of controlling errors which took place during the transmission. More particularly, the packets received in the order of the sequence are delivered to an output multiplex 31. On the other hand, if the packet received does not have the required sequence number in the sequence notably because of a loss of one or more packets, it is not delivered to the output multiplex 31 as long as the lost packet or packets have not been received or as long as the maximum waiting time has not expired.
This error control method is generally known as Selective-Repeat ARQ. The implementation of this method is illustrated in FIG. 2. The left-hand part of this FIG. 2 is a diagram showing, at the transmitter, the transmission of packets as a function of time (the time elapses downwards) and the right-hand part is a diagram showing, at the receiver, the reception of transmitted packets also as a function of time. As for the central part, this depicts the transmission of the packets over the transmission line.
Two virtual circuits VC-xcex1 and VC-xcex2 are multiplexed on the transmission line between the transmitter and receiver. Each packet transmitted over the transmission line bears a sequence number which identifies it, in the sequence of transmitted packets, with respect to the preceding ones and the following ones.
As can be seen in this diagram, the packet I0 (the first packet in a sequence of packets) which belongs to the second virtual circuit VC-xcex2 has been received correctly. This packet I0 is then delivered to the output multiplex 31.
The packet I1 on the other hand has been lost and is therefore not received by the receiver 30. On reception of the packet I2, the receiver 30 notes that the sequence number in the sequence is not the one required. It is in fact 2 whereas it is the packet I1, and therefore with the sequence number 1, which is expected. The receiver 30 therefore sends to the transmitter 10 a negative acknowledgement NAK1 thus requesting the transmitter 10 to re-transmit the packet I1.
As for the packets I2 to I4, they have been correctly received by the receiver. However, because the packet I1 has not been correctly received, they too are not delivered and are then stored whilst awaiting their delivery. It will also be said that they are kept.
After the transmission of the packet I4, the transmitter 10 receives the negative acknowledgement NAK1 concerning the packet I1 and consequently re-transmits this packet I1, which is received later at the receiver. As can be noted, the receiver delivers to the output multiplex not only the packet I1 but also the packets I2 to I4 which had been kept up till now.
Thus, according to this method, the packets which have been received after the loss of a packet are not delivered and are kept, until the packet is correctly received.
It is possible that the packet I1 may not always be correctly received by the receiver 30. Conventionally, the packets I2, I3 and I4 are then delivered after the expiry of a predetermined time, referred to as the maximum waiting time.
It will be noted that such a process requires only the sequence number of sending of the packets in the current sequence in order to function correctly.
However, when several virtual circuits are multiplexed on one and the same transmission link between a transmitter and receiver, it may happen that packets belonging to one virtual circuit are kept because a packet belonging to another virtual circuit has been lost. This eventuality is also illustrated in FIG. 2, where it can be seen that the packets I1 and I4 belong to the same virtual circuit VC-xcex1 and that the packets I0, I2 and I3 belong to the other virtual circuit VC-xcex2. The packets I2 and I3 of the virtual circuit VC-xcex2 are kept whereas, with regard to this circuit VC-xcex2, no packet has been lost. Thus the lost packet I1 belonging to the virtual circuit VC-xcex1 blocks the delivery of the packets of the virtual circuit VC-xcex2.
In order to solve this problem, a method is known from U.S. Pat. No. 4,726,027 document for a Go-Back-N protocol. According to this method, at the transmitter side, each packet is allocated with two indices : one is an identifier of the logical link to which the packet belongs and the other is the order of transmission of the packet regarding this logical link. When a packet is not correctly received, a negative acknowledgement is sent to the transmitter in order to retransmit it. Only the successively received packets which belong to the same program application are discarded, the others being delivered.
FIG. 3 shows an example of an application of this method modified to be applied as a Selective Repeat protocol.
In this FIG. 3, the packet Ixcex20 belonging to a virtual circuit VC-xcex2 is correctly received and is delivered. The packet Ixcex10 belonging to an another virtual circuit VC-xcex1 is not received.
Contrary to the preceding scheme, although the preceding packet Ixcex10 has not been received, the packet Ixcex21 belonging to the virtual circuit VC-xcex2 is delivered since it is correctly received.
Note that the receiver doesn""t still notice that packet Ixcex10 is not correctly received. It does when the packet Ixcex11 belonging to the same virtual circuit as the lost packet Ixcex10 is received. Then, the packet Ixcex11 is kept and a negative acknowledgement NAKxcex10 is sent to the transmitter for retransmission. When packet LaO is correctly received, the packets xcex10 and xcex11 are delivered.
Although the U.S. Pat. No. 4,726,027 overcome the problem raised above, the drawback of the method is the delay for the receiver to notice that a packet from a virtual circuit is not correctly received.
Furthermore, this method would need to transmit a packet with an identifier of the virtual circuit and its order of transmission for that virtual circuit, which generally requests a too large number of bits.
Furthermore, this method would need to modify the Selective Repeat ARQ protocol at both transmitter and receiver sides in order to be aware of the logical link to which a retransmitted packet belongs.
The aim of the present invention is therefore to resolve the above-mentioned problems in the case of multiplexing of several virtual circuits on the transmission link.
In order to achieve these aims, the method of the present invention consists, at the transmitter side, in allocating, to each packet to be transmitted over the or a transmission line, two indices, one giving the sequence number of the said packet and the other enabling said packet to point to the last packet which was previously transmitted belonging to the same virtual circuit as the said packet, and, at the receiver side, in determining, on a correct reception of a packet, the packet pointed to by the said received packet, and, if this packet pointed to has been delivered to the output multiplex, then delivering the said received packet, otherwise not delivering it.
According an another characteristic of the present invention, the method consists, at the receiver side, in keeping the packets which are not delivered and, in delivering, when correctly received, a re-transmitted packet and then in seeking amongst the keeping packets the one, if it exists, which points to said retransmitted packet and then delivering it, and once again in seeking, if it exists, the packet which points to the latter packet and delivering it and so on until there is no packet which points to the one delivered previously.